package com.wfm.niuke.tree;

import com.wfm.common.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

public class BM35判断是不是完全二叉树 {
    public boolean isCompleteTree (TreeNode root) {
        //空树一定是完全二叉树
        if (root == null)
            return true;
        //定义一个首次出现的标记位
        boolean notComplete = false;

        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int curSize = q.size();
            for (int i = 0; i < curSize; i++) {
                TreeNode poll = q.poll();
                //标记第一次遇到空节点
                if (poll == null) {
                    notComplete = true;
                    continue;
                }
                //后续访问已经遇到空节点了，说明经过了叶子
                if (notComplete)
                    return false;
                q.offer(poll.left);
                q.offer(poll.right);
            }
        }
        return true;
    }

}
